package 回溯法.DFS;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: ywk
 * @date: 2020-12-19
 */
public class N皇后问题 {
    static List<Character[][]> res = new ArrayList<>(); /* 输⼊棋盘边⻓ n，返回所有合法的放置 */


    static List<Character[][]> solveNQueens(int n) {
        // '.' 表⽰空，'Q' 表⽰皇后，初始化空棋盘。
        Character[][] board = new Character[n][n];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = '.';
            }
        }
        backtrack(board, 0);
        return res;
    }

    // 路径：board 中⼩于 row 的那些⾏都已经成功放置了皇后
    // 选择列表：第 row ⾏的所有列都是放置皇后的选择
    // 结束条件：row 超过 board 的最后⼀⾏
    static void backtrack(Character[][] board, int row) {

        // 触发结束条件
        if (row == board.length) {
            Character[][] characters = arrayCopy(board);
            res.add(characters);
            return;
        }
        int n = board[row].length;
        for (int col = 0; col < n; col++) {
            // 排除不合法选择,进行剪枝
            if (!isValid(board, row, col)) continue;
            // 做选择
            board[row][col] = '*';
            // 进⼊下⼀⾏决策
            backtrack(board, row + 1);
            // 撤销选择
            board[row][col] = '.';
        }
    }

    /* 是否可以在 board[row][col] 放置皇后 */
    static boolean isValid(Character[][] board, int row, int col) {
        int n = board.length;
        // 检查列是否有皇后互相冲突
        for (int i = 0; i < n; i++) {
            if (board[i][col] == '*') return false;
        }
        // 检查右上⽅是否有皇后互相冲突
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == '*') return false;
        }
        // 检查左上⽅是否有皇后互相冲突
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == '*') return false;
        }
        return true;
    }

    public static void printQ(List<Character[][]> res) {
        for (int index = 0; index < res.size(); index++) {
            Character[][] board = res.get(index);
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    System.out.print(board[i][j]+" ");
                }
                System.out.println();
            }
            System.out.println();
        }

    }

    public static Character[][] arrayCopy(Character[][] board) {
        Character[][] res = new Character[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                res[i][j] = board[i][j];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        printQ(solveNQueens(6));

    }
}
